二叉树之Java实现二叉树基本操作 - CSDN博客

创建时间：2018/3/19 13:43
来源：http://blog.csdn.net/fengrunche/article/details/52305748


二叉树之Java实现二叉树基本操作

参考自《Java数据结构与算法》

  • 定义一个节点类，使节点与二叉树操作分离

  1. class Node {  
  2.     int  value;  
  3.     Node leftChild;  
  4.     Node rightChild;  
  5.       
  6.     Node(int value) {  
  7.         this.value = value;  
  8.     }  
  9.       
  10.     public void display() {  
  11.         System.out.print(this.value + "\t");  
  12.     }  
  13.   
  14.     @Override  
  15.     public String toString() {  
  16.         // TODO Auto-generated method stub  
  17.         return String.valueOf(value);  
  18.     }  
  19. }  

  • 需要实现的二叉树操作

  1. class BinaryTree {  
  2.     private Node root = null;  
  3.       
  4.     BinaryTree(int value) {  
  5.         root = new Node(value);  
  6.         root.leftChild  = null;  
  7.         root.rightChild = null;  
  8.     }  
  9.     public Node findKey(int value) {}   //查找  
  10.         public String insert(int value) {}  //插入  
  11.         public void inOrderTraverse() {}    //中序遍历递归操作  
  12.         public void inOrderByStack() {}     //中序遍历非递归操作      
  13.         public void preOrderTraverse() {}  //前序遍历  
  14.         public void preOrderByStack() {}   //前序遍历非递归操作  
  15.         public void postOrderTraverse() {} //后序遍历  
  16.         public void postOrderByStack() {}  //后序遍历非递归操作  
  17.         public int getMinValue() {} //得到最小(大)值  
  18.         public boolean delete(int value) {} //删除  
  19. }  

  • 查找数据：

  1.  public Node findKey(int value) {  
  2.     Node current = root;  
  3.     while (true) {  
  4.         if (value == current.value) {  
  5.             return current;  
  6.         } else if (value < current.value) {  
  7.             current = current.leftChild;  
  8.         } else if (value > current.value) {  
  9.             current = current.rightChild;  
  10.         }  
  11.           
  12.         if (current == null) {  
  13.             return null;  
  14.         }  
  15.     }  
  16. }  

  • 插入数据：与查找数据类似，不同点在于当节点为空时，不是返回而是插入

  1. public String insert(int value) {  
  2. String error = null;  
  3.   
  4. Node node = new Node(value);  
  5. if (root == null) {  
  6.     root = node;  
  7.     root.leftChild  = null;  
  8.     root.rightChild = null;  
  9. } else {  
  10.     Node current = root;  
  11.     Node parent = null;  
  12.     while (true) {  
  13.         if (value < current.value) {  
  14.             parent = current;  
  15.             current = current.leftChild;  
  16.             if (current == null) {  
  17.                 parent.leftChild = node;  
  18.                 break;  
  19.             }  
  20.         } else if (value > current.value) {  
  21.             parent = current;  
  22.             current = current.rightChild;  
  23.             if (current == null) {  
  24.                 parent.rightChild = node;  
  25.                 break;  
  26.             }  
  27.         } else {  
  28.             error = "having same value in binary tree";  
  29.         }     
  30.     } // end of while  
  31. }  
  32. return error;  
  33.   }  

  • 遍历数据：

            1）中序遍历：最常用的一种遍历方法

  1.  /** 
  2.  * //中序遍历(递归)： 
  3.  *    1、调用自身来遍历节点的左子树 
  4.  *    2、访问这个节点 
  5.  *    3、调用自身来遍历节点的右子树 
  6.  */  
  7. public void inOrderTraverse() {  
  8.     System.out.print("中序遍历:");  
  9.     inOrderTraverse(root);  
  10.     System.out.println();  
  11. }  
  12.   
  13. private void inOrderTraverse(Node node) {  
  14.     if (node == null)   
  15.         return ;  
  16.       
  17.     inOrderTraverse(node.leftChild);  
  18.     node.display();  
  19.     inOrderTraverse(node.rightChild);  
  20. }  

               

  1. /** 
  2.      * 中序非递归遍历： 
  3.      *     1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。 
  4.      *     2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current 
  5.      *     3) 重复1、2步操作，直到current为空且栈内节点为空。 
  6.      */  
  7.     public void inOrderByStack() {  
  8.         System.out.print("中序非递归遍历:");  
  9.         Stack<Node> stack = new Stack<Node>();  
  10.         Node current = root;  
  11.         while (current != null || !stack.isEmpty()) {  
  12.             while (current != null) {  
  13.                 stack.push(current);  
  14.                 current = current.leftChild;  
  15.             }  
  16.               
  17.             if (!stack.isEmpty()) {  
  18.                 current = stack.pop();  
  19.                 current.display();  
  20.                 current = current.rightChild;  
  21.             }  
  22.         }  
  23.         System.out.println();  
  24.     }  

              2）前序遍历：

  1.  /** 
  2.  * //前序遍历(递归)： 
  3.  *    1、访问这个节点 
  4.  *    2、调用自身来遍历节点的左子树 
  5.  *    3、调用自身来遍历节点的右子树 
  6.  */  
  7. public void preOrderTraverse() {  
  8.     System.out.print("前序遍历:");  
  9.     preOrderTraverse(root);  
  10.     System.out.println();  
  11. }  
  12.   
  13. private void preOrderTraverse(Node node) {  
  14.     if (node == null)   
  15.         return ;  
  16.       
  17.     node.display();  
  18.     preOrderTraverse(node.leftChild);  
  19.     preOrderTraverse(node.rightChild);  
  20. }  

               

  1. /** 
  2.      * 前序非递归遍历： 
  3.      *     1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。 
  4.      *     2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current 
  5.      *     3) 重复1、2步操作，直到current为空且栈内节点为空。 
  6.      */  
  7.     public void preOrderByStack() {  
  8.         System.out.print("前序非递归遍历:");  
  9.         Stack<Node> stack = new Stack<Node>();  
  10.         Node current = root;  
  11.         while (current != null || !stack.isEmpty()) {  
  12.             while (current != null) {  
  13.                 stack.push(current);  
  14.                 current.display();  
  15.                 current = current.leftChild;  
  16.             }  
  17.               
  18.             if (!stack.isEmpty()) {  
  19.                 current = stack.pop();  
  20.                 current = current.rightChild;  
  21.             }  
  22.         }  
  23.         System.out.println();  
  24.     }  

             3）后序遍历：

  1.  /** 
  2.  * //后序遍历(递归)： 
  3.  *    1、调用自身来遍历节点的左子树 
  4.  *    2、调用自身来遍历节点的右子树 
  5.  *    3、访问这个节点 
  6.  */  
  7. public void postOrderTraverse() {  
  8.     System.out.print("后序遍历:");  
  9.     postOrderTraverse(root);  
  10.     System.out.println();  
  11. }  
  12.   
  13. private void postOrderTraverse(Node node) {  
  14.     if (node == null)   
  15.         return ;  
  16.       
  17.     postOrderTraverse(node.leftChild);  
  18.     postOrderTraverse(node.rightChild);  
  19.     node.display();  
  20. }  
  1. /** 
  2.      * 后序非递归遍历： 
  3.      *     1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。 
  4.      *     2）若左子树为空，取栈顶节点的右子树，如果右子树为空或右子树刚访问过，则访问该节点，并将preNode置为该节点 
  5.      *     3) 重复1、2步操作，直到current为空且栈内节点为空。 
  6.      */  
  7.     public void postOrderByStack() {  
  8.         System.out.print("后序非递归遍历:");  
  9.         Stack<Node> stack = new Stack<Node>();  
  10.         Node current = root;  
  11.         Node preNode = null;  
  12.         while (current != null || !stack.isEmpty()) {  
  13.             while (current != null) {  
  14.                 stack.push(current);  
  15.                 current = current.leftChild;  
  16.             }  
  17.               
  18.             if (!stack.isEmpty()) {  
  19.                 current = stack.peek().rightChild;  
  20.                 if (current == null || current == preNode) {  
  21.                     current = stack.pop();  
  22.                     current.display();  
  23.                     preNode = current;  
  24.                     current = null;  
  25.                 }  
  26.             }  
  27.         }  
  28.         System.out.println();  
  29.     }  


  • 得到最小(大)值：依次向左(右)直到空为之
  1. public int getMinValue() {  
  2. Node current = root;  
  3. while (true) {  
  4.     if (current.leftChild == null)  
  5.         return current.value;  
  6.       
  7.     current = current.leftChild;  
  8. }  
  • 删除：删除操作很复杂，删除节点大致分为三种情况：
             1）删除节点为叶子节点

               

              2）删除节点只有一个子节点：只有一个左子节点和只有一个右子节点

               

              3）删除节点有两个子节点：这种情况比较复杂，需要寻找后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。

            说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。

            得到后继节点的代码如下：

  1.  /** 
  2.  *  
  3.  * 得到后继节点，即删除节点的左后代 
  4.  */  
  5. private Node getSuccessor(Node delNode) {  
  6.     Node successor = delNode;  
  7.     Node successorParent = null;  
  8.     Node current = delNode.rightChild;  
  9.       
  10.     while (current != null) {  
  11.         successorParent = successor;  
  12.         successor = current;  
  13.         current = current.leftChild;  
  14.     }  
  15.       
  16.     //如果后继节点不是删除节点的右子节点时，  
  17.     if (successor != delNode.rightChild) {  
  18.         //要将后继节点的右子节点指向后继结点父节点的左子节点，  
  19.         successorParent.leftChild = successor.rightChild;  
  20.         //并将删除节点的右子节点指向后继结点的右子节点  
  21.         successor.rightChild = delNode.rightChild;  
  22.     }  
  23.     //任何情况下，都需要将删除节点的左子节点指向后继节点的左子节点  
  24.     successor.leftChild = delNode.leftChild;  
  25.       
  26.     return successor;  
  27. }  
                 a)如果后继节点是刚好是要删除节点的右子节点（此时可以知道，这个右子节点没有左子点，如果有，就不该这个右子节点为后继节点）

          

            

  1. //删除的节点为父节点的左子节点时：  
  2. parent.leftChild = successor;  
  3. successor.leftChild = delNode.leftChild;  
  4.        
  5. //删除的节点为父节点的右子节点时：  
  6. parent.rightChild = successor;  
  7. successor.leftChild = delNode.leftChild  




             b)如果后继节点为要删除节点的右子节点的左后代：


 
            


 
           


  1. //删除的节点为父节点的左子节点时：  
  2.  successorParent.leftChild = successor.rightChild;  
  3.  successor.rightChild = delNode.rightChild;  
  4.   parent.leftChild = successor;  
  5.   successor.leftChild = delNode.leftChild;  
  6.         
  7.   //删除的节点为父节点的右子节点时：  
  8.   successorParent.leftChild = successor.rightChild;  
  9.   successor.rightChild = delNode.rightChild;  
  10.   parent.rightChild = successor;  
  11.   successor.leftChild = delNode.leftChild;  




                综合以上各种情况，删除代码如下：





  1.  public boolean delete(int value) {  
  2.     Node current = root;    //需要删除的节点  
  3.     Node parent = null;     //需要删除的节点的父节点  
  4.     boolean isLeftChild = true;   //需要删除的节点是否父节点的左子树  
  5.       
  6.     while (true) {  
  7.         if (value == current.value) {  
  8.             break;  
  9.         } else if (value < current.value) {  
  10.             isLeftChild = true;  
  11.             parent = current;  
  12.             current = current.leftChild;  
  13.         } else {  
  14.             isLeftChild = false;  
  15.             parent = current;  
  16.             current = current.rightChild;  
  17.         }  
  18.           
  19.         //找不到需要删除的节点，直接返回  
  20.         if (current == null)  
  21.             return false;  
  22.     }  
  23.       
  24.     //分情况考虑  
  25.     //1、需要删除的节点为叶子节点  
  26.     if (current.leftChild == null && current.rightChild == null) {  
  27.         //如果该叶节点为根节点，将根节点置为null  
  28.         if (current == root) {  
  29.             root = null;  
  30.         } else {  
  31.             //如果该叶节点是父节点的左子节点，将父节点的左子节点置为null  
  32.             if (isLeftChild) {  
  33.                 parent.leftChild  = null;  
  34.             } else { //如果该叶节点是父节点的右子节点，将父节点的右子节点置为null  
  35.                 parent.rightChild = null;  
  36.             }  
  37.         }  
  38.     }   
  39.     //2、需要删除的节点有一个子节点，且该子节点为左子节点  
  40.     else if (current.rightChild == null) {  
  41.         //如果该节点为根节点，将根节点的左子节点变为根节点  
  42.         if (current == root) {  
  43.             root = current.leftChild;  
  44.         } else {  
  45.             //如果该节点是父节点的左子节点，将该节点的左子节点变为父节点的左子节点  
  46.             if (isLeftChild) {  
  47.                 parent.leftChild = current.leftChild;  
  48.             } else {  //如果该节点是父节点的右子节点，将该节点的左子节点变为父节点的右子节点  
  49.                 parent.rightChild = current.leftChild;  
  50.             }  
  51.         }  
  52.     }  
  53.     //2、需要删除的节点有一个子节点，且该子节点为右子节点  
  54.     else if (current.leftChild == null) {  
  55.         //如果该节点为根节点，将根节点的右子节点变为根节点  
  56.         if (current == root) {  
  57.             root = current.rightChild;  
  58.         } else {  
  59.             //如果该节点是父节点的左子节点，将该节点的右子节点变为父节点的左子节点  
  60.             if (isLeftChild) {  
  61.                 parent.leftChild = current.rightChild;  
  62.             } else {  //如果该节点是父节点的右子节点，将该节点的右子节点变为父节点的右子节点  
  63.                 parent.rightChild = current.rightChild;  
  64.             }  
  65.         }  
  66.     }  
  67.     //3、需要删除的节点有两个子节点，需要寻找该节点的后续节点替代删除节点  
  68.     else {  
  69.         Node successor = getSuccessor(current);  
  70.         //如果该节点为根节点，将后继节点变为根节点，并将根节点的左子节点变为后继节点的左子节点  
  71.         if (current == root) {  
  72.             root = successor;  
  73.         } else {  
  74.             //如果该节点是父节点的左子节点，将该节点的后继节点变为父节点的左子节点  
  75.             if (isLeftChild) {  
  76.                 parent.leftChild = successor;  
  77.             } else {  //如果该节点是父节点的右子节点，将该节点的后继节点变为父节点的右子节点  
  78.                 parent.rightChild = successor;  
  79.             }  
  80.         }  
  81.     }  
  82.     current = null;  
  83.     return true;  
  84. }  




  •                测试代码
  1.     public class BinaryTreeDemo {  
  2.         public static void main(String[] args) {  
  3.         BinaryTree bt = new BinaryTree(52);  
  4.         bt.insert(580);  
  5.         bt.insert(12);  
  6.         bt.insert(50);  
  7.         bt.insert(58);  
  8.         bt.insert(9);  
  9.         bt.insert(888);  
  10.         bt.insert(248);  
  11.         bt.insert(32);  
  12.         bt.insert(666);  
  13.         bt.insert(455);  
  14.         bt.insert(777);  
  15.         bt.insert(999);  
  16.         bt.inOrderTraverse();  
  17.         bt.preOrderTraverse();  
  18.         bt.postOrderTraverse();  
  19.         System.out.println(bt.findKey(32));  
  20.         System.out.println(bt.findKey(81));  
  21.         System.out.println("最小值:" + bt.getMinValue());  
  22. //      bt.delete(32);      //删除叶子节点  
  23. //      bt.delete(50);      //删除只有一个左子节点的节点  
  24. //      bt.delete(248);      //删除只有一个右子节点的节点  
  25. //      bt.delete(248);      //删除只有一个右子节点的节点  
  26. //      bt.delete(580);      //删除有两个子节点的节点，且后继节点为删除节点的右子节点的左后代  
  27. //      bt.delete(888);      //删除有两个子节点的节点，且后继节点为删除节点的右子节点  
  28.         bt.delete(52);       //删除有两个子节点的节点，且删除节点为根节点  
  29.           
  30.         bt.inOrderTraverse();  
  31.         }  
  32.     }  
测试结果：



中序遍历:91232
50 52 
58248455580
666777 
888999 


中序非递归遍历:9 12 
32 50 5258248
455580 
666777 
888999 


前序遍历:52 12 
9 50 3258058
248 455
888 666
777 999


前序非递归遍历:52 12 
9 50 3258058
248 455
888 666
777 999


后序遍历:9 32 
50 12 45524858
777 666
999 888
580 52 


后序非递归遍历:9 32 
50 12 45524858
777 666
999 888
580 52 


32

null

最小值:9

中序遍历:9 12 
32 50 58248455580
666777 
888999